import Data.List

sumPower :: Int -> Int -> Int
sumPower n k = sum (map (\x -> x^k)  [1..n])

shrink :: Char -> String -> String
shrink c s = concat $ map (\x -> if (c `elem` x) then [c] else x) $ group s

stretch :: Char -> Integer -> String -> String
stretch c n s
  | n <= 0 = error "fuck you"
  | otherwise = concat $ map (\x -> if c == x then replicate (fromInteger n) c else [x]) s


myodds :: [Int] -> [Int]
myodds ls = [ x | x <- ls, not (odd x)]


extract :: String -> [String]
extract str = scanr (\a b -> if a == '1' || a == '0' then (a : b) else b) [] str

mymax :: Ord a => [a] -> a
mymax ls = foldl1 (\a b -> if b > a then b else a) ls

binDigit '1' = 1
binDigit '0' = 0
binDigit _ = error "you fucking idiot"

binaryToDecimal :: String -> Integer
binaryToDecimal str = snd $ foldr (\b (i,x) -> (i+1, x + (binDigit b) * 2^i)) (0,0) str

binaryToDecimal' str = sum $ zipWith (*) binDigits binPowers
  where
    binDigits = reverse (map binDigit str)
    binPowers = [2^i | i <- [0..]]

decimalToBinary :: Integer -> String
decimalToBinary 0 = "0"
decimalToBinary n
  | m == 0 = "1"
  | n' == 0 = decimalToBinary m ++ "0"
  | n' == 1 = decimalToBinary m ++ "1"
  where
    n' = n `mod` 2
    m = n `div` 2


-----------------------------------------------------------------------------------

data IntList = Cons Int IntList | Empty
             deriving Show

intListLength :: IntList -> Int
intListLength Empty = 0
intListLength (Cons _ ls) = 1 + (intListLength ls)

maxIntList :: IntList -> Int
maxIntList Empty = error "you motherfucking asshole, die you sucker fucker!"
maxIntList (Cons i Empty) = i
maxIntList (Cons i ls)
  | i > m = i
  | otherwise = m
  where
    m = maxIntList ls

sumIntList :: IntList -> Int
sumIntList Empty = 0
sumIntList (Cons i ls) = i + sumIntList ls

filterOdd :: IntList -> IntList
filterOdd Empty = Empty
filterOdd (Cons i ls)
  | odd i = Cons i (filterOdd ls)
  | otherwise = filterOdd ls


----------------------------------------------------------------------------------

data BinaryTree a = Node a (BinaryTree a) (BinaryTree a) | Leaf

instance Show a => Show (BinaryTree a) where
  show _ = "fuck you"

f = (\x -> \y -> \z -> (x y, x (x z)))
x1 = (reverse . take 2 . words . \k -> "Max Mustermann" ++ k) "!!!"

instance Eq (BinaryTree a) where
  (==) Leaf Leaf = True
  (==) (Node _ _ _) Leaf = False
  (==) Leaf (Node _ _ _) = False
  (==) (Node _ l1 r1) (Node _ l2 r2) = l1 == l2 && r1 == r2

t1 = (Node 1 ((Node 2 (Leaf) (Leaf))) (Node 3 (Leaf) (Node 4 (Leaf) (Leaf))))
t2 = (Node 1 ((Node 2 (Leaf) (Leaf))) (Node 3 (Leaf) (Node 1 (Leaf) (Node 1 Leaf Leaf))))
t3 = (Node 2 ((Node 10 (Leaf) (Leaf))) (Node 9 (Leaf) (Node 4 (Leaf) (Leaf))))

depth :: BinaryTree a -> Int
depth Leaf = 0
depth (Node _ li re) = 1 + max liDepth reDepth
  where
    liDepth = depth li
    reDepth = depth re

treeSum :: Num a => BinaryTree a -> a
treeSum Leaf = 0
treeSum (Node i li re) = i + liSum + reSum
  where
    liSum = treeSum li
    reSum = treeSum re

data TTree a = TNode a (TTree a) (TTree a) (TTree a) | Nil

geordnet :: (Ord a) => TTree a -> Bool
geordnet Nil = True
geordnet (TNode x t1 t2 t3) = geordnet t1 && geordnet t2 && geordnet t3 &&
                             f x t1 && f x t2 && f x t3
  where
    f e (TNode e' _ _ _) = e < e'
    f _ Nil = True


elems Nil = []
elems (TNode x li mi re) = [x] ++ (elems li) ++ (elems mi) ++ (elems re)

geordnet' :: (Ord a) => TTree a -> Bool
geordnet' Nil = True
geordnet' (TNode x li mi re)
  | x < minimum subElems = geordnet li && geordnet mi && geordnet re
  | otherwise = False
  where
    subElems = (elems li) ++ (elems mi) ++ (elems re)


alleGroesser :: (Ord a) => TTree a -> a -> [a]
alleGroesser Nil _ = []
alleGroesser (TNode x li mi re) y
  | x > y = x : elems
  | otherwise = elems
    where
      elems = (alleGroesser li y) ++ (alleGroesser mi y) ++ (alleGroesser re y)


btreeElems :: BinaryTree a -> [a]
btreeElems Leaf = []
btreeElems (Node x li re) = x : (btreeElems li ++ btreeElems re)

allDistinct :: (Eq a) => BinaryTree a -> Bool
allDistinct Leaf = True
allDistinct (Node x li re)
  | x `elem` liElems || x `elem` reElems = False
  | otherwise = allDistinct li && allDistinct re
  where
    liElems = btreeElems li
    reElems = btreeElems re

------------------------------------------------------------------------------

data Nat = Z | S Nat

plusNat :: Nat -> Nat -> Nat
plusNat Z z2 = z2
plusNat (S a) b = plusNat a (S b)

timesNat :: Nat -> Nat -> Nat
timesNat Z z2 = Z
timesNat (S a) b = plusNat b (timesNat a b)

eqNat :: Nat -> Nat -> Bool
eqNat Z Z = True
eqNat Z (S _) = False
eqNat (S _) Z = False
eqNat (S z1) (S z2) = eqNat z1 z2


grNat :: Nat -> Nat -> Bool
grNat Z Z = False
grNat Z (S _) = False
grNat (S _) Z = True
grNat (S z1) (S z2) = grNat z1 z2


instance Show Nat where
  show z = show $ natToInt z
    where
      natToInt Z = 0
      natToInt (S z1) = 1 + (natToInt z1)


getOddNats :: [Nat] -> [Nat]
getOddNats ls = filter oddNat ls

oddNat :: Nat -> Bool
oddNat Z = False
oddNat (S Z) = True
oddNat (S (S z)) = oddNat z

natInt Z = 0
natInt (S z1) = 1 + (natInt z1)

intNat :: Int -> Nat
intNat 0 = Z
intNat 1 = (S Z)
intNat n = S (intNat (n-1))

sortNats :: [Nat] -> [Nat]
sortNats [] = []
sortNats ls = map intNat $ sort $ map natInt ls

--------------------------------------------------------------------------------

f1 =  (\x -> \y -> (x (y x), x, y))

data NumTree  = NTEmpty | NT Integer NumTree NumTree NumTree
                         deriving Show

aufsteigen :: NumTree -> Bool
aufsteigen NTEmpty = True
aufsteigen (NT x li mi ri)= y && z && u &&
                            (checkTree li mi) && (checkTree mi ri)
  where
    y = checkElem x li
    z = checkElem x mi
    u = checkElem x ri

checkElem :: Integer -> NumTree -> Bool
checkElem _ NTEmpty = True
checkElem x (NT y lli mmi rri) = (x < y) && (checkElem x lli) &&(checkElem x mmi) && (checkElem x rri)

checkTree :: NumTree -> NumTree -> Bool
checkTree  NTEmpty t2 = True
checkTree (NT y li mi ri) t2 = (checkElem y t2) && (checkTree li t2) && (checkTree mi t2) && (checkTree ri t2)

ttree = NT 1 (NT 2 NTEmpty NTEmpty NTEmpty) (NT 3 NTEmpty (NT 4 NTEmpty NTEmpty NTEmpty) NTEmpty) (NT 1 NTEmpty NTEmpty NTEmpty)
